import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
    int curPreIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> value2InIndex = makeValue2InIndex(inorder);
        return build(preorder, value2InIndex, preorder.length - 1, 0);
    }

    private Map<Integer, Integer> makeValue2InIndex(int[] inorder) {
        Map<Integer, Integer> value2inIndex = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            value2inIndex.put(inorder[i], i);
        }
        return value2inIndex;
    }

    TreeNode build(int[] preorder, Map<Integer, Integer> value2InIndex, int maxPreIndex, int inStart) {
        if (curPreIndex > maxPreIndex) {
            return null;
        }
        int rootValue = preorder[curPreIndex++];
        TreeNode root = new TreeNode(rootValue);
        int rootInIndex = value2InIndex.get(rootValue);
        int leftLen = rootInIndex - inStart;
        root.left = build(preorder, value2InIndex, curPreIndex + leftLen - 1, inStart);
        root.right = build(preorder, value2InIndex, maxPreIndex, rootInIndex + 1);
        return root;
    }
}

//迭代
class Solution1 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int curPreIndex = 0, curInIndex = 0;
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode root = new TreeNode(preorder[curPreIndex++]);
        stack.push(root);
        while (curPreIndex < preorder.length) {
            TreeNode parent = stack.peek();
            TreeNode cur = new TreeNode(preorder[curPreIndex]);
            if (parent.val != inorder[curInIndex]) {
                parent.left = cur;
            } else {
                stack.pop();
                curInIndex++;
                while (!stack.isEmpty() && stack.peek().val == inorder[curInIndex]) {
                    parent = stack.pop();
                    curInIndex++;
                }
                parent.right = cur;
            }
            stack.push(cur);
            curPreIndex++;
        }
        return root;
    }
}